package 题目集.滑动窗口.ch02_不定长窗口;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
 * 题目大意：给你一个数组nums，一个数K。你每次可以取数组最左侧或最右侧的一个数，问最少需要取多少次，可以使得取出来的数之和=x
 */
public class ch07_将x减到0的最小操作数 {

    /**
     * 第一思路：区间dp,有3个参数，左右区间端点，以及要凑成的数k
     * 第三个参数可以优化掉，通过前缀和快速求左右区间的和，来判断是否和为k，这样第三个参数就变成了常量（所以可以去掉）
     * 时间复杂度n^2
     * <p>
     * 第二思路：滑动窗口，可以把问题转化为从 nums 中移除一个最长的子数组，使得剩余元素的和为 x,即寻找一个长度最大，且和为sum-x的窗口
     */

    public int minOperations(int[] nums, int x) {
        int k = Arrays.stream(nums).sum() - x;
        if (k < 0) return -1;   //整个数组都凑不出x
        int cur = 0;
        int ans = -1;
        for (int i = 0, j = 0; j < nums.length; j++) {
            cur += nums[j];
            while (cur > k && i <= j) cur -= nums[i++];
            if (cur == k) ans = Math.max(ans, j - i + 1);
        }
        return ans == -1 ? -1 : nums.length - ans;
    }

    @Test
    public void t1() {
        int[] arr = {1, 1};
        int k = 4;
        System.out.println(minOperations(arr, k));
    }

    @Test
    public void t2() {
        int[] arr = {1, 1, 4, 2, 3};
        int k = 5;
        System.out.println(minOperations(arr, k));
    }

}
